W5. Лемма о накачке для регулярных языков, автоматы с магазином (PDA)

1. Краткое содержание

1.1 Почему некоторые языки не регулярны

Напомним: регулярный язык — это любой язык, который может быть распознан конечным автоматом (FSA). FSA — мощный инструмент, но у него принципиальное ограничение: есть лишь фиксированная конечная память — ровно текущее состояние. У FSA с \(n\) состояниями можно «помнить» только то, в каком из этих \(n\) состояний он находится, и не больше.

Из этого следует, что FSA не справляются с шаблонами, где нужно считать до произвольной глубины. Например:

• \(L = \{a^n b^n \mid n \geq 1\}\): чтобы распознать этот язык, машина должна сосчитать \(n\) символов a, а затем проверить ровно \(n\) символов b. Сколько бы состояний ни было у FSA, при достаточно большом \(n\) «памяти» не хватит.
• \(L = \{ww^R \mid w \in \{a,b\}^*\}\): палиндромы чётной длины. Здесь нужно запомнить всю первую половину строки, а она может быть сколь угодно длинной.

Чтобы доказать регулярность языка, достаточно выписать работающий FSA. Чтобы доказать нерегулярность, задача сложнее: нужно показать, что ни один FSA язык не распознаёт. Перебрать все автоматы невозможно. Вместо этого используют лемму о накачке (Pumping Lemma).

1.2 Принцип голубятни

Перед формулировкой леммы о накачке нужен классический принцип голубятни (Pigeonhole Principle):

Если \(n\) голубей разложили по \(m\) голубятням и \(n > m\), то в каком-то голубятне окажется не меньше двух голубей.

Принцип голубятни для автомата: визитов больше, чем состояний — значит, есть повтор состояния

Применение к FSA: состояния автомата — это «ящики», а переходы, пройденные при чтении строки, — «голуби». Если длина строки больше числа состояний \(|Q|\), то при обработке автомат посещает больше \(|Q|\) состояний (с повторениями). Различных состояний только \(|Q|\), значит какое-то состояние посещено дважды. Повторное состояние соответствует циклу в автомате.

1.3 У бесконечного регулярного языка обязан быть цикл

Пусть бесконечный регулярный язык \(L\) распознаётся FSA с \(m\) состояниями. Так как \(L\) бесконечен, в нём есть строки сколь угодно большой длины. Когда FSA обрабатывает достаточно длинную строку (больше \(m\) символов), он совершает больше \(m\) переходов. По принципу голубятни какое-то состояние \(q\) повторяется.

Длинный принимающий путь содержит петлю, которую можно накачивать

Тогда путь автомата выглядит так: \[\text{start} \xrightarrow{\text{read } x} q \xrightarrow{\text{read } y} q \xrightarrow{\text{read } z} \text{accept}\] где \(y\) — строка, по которой мы «зациклились» в \(q\). Важно: так как машина детерминирована и \(y\) возвращает в \(q\), по этому циклу можно пройти любое число раз: \[x y^0 z, \quad x y^1 z, \quad x y^2 z, \quad x y^3 z, \quad \ldots\] все ведут в то же принимающее состояние. Следовательно, все эти строки лежат в \(L\).

1.4 Лемма о накачке для регулярных языков

1.4.1 Формулировка

Лемма о накачке: если \(L \subseteq \Sigma^*\) — регулярный язык, то существует целое \(m \geq 1\) (длина накачки / критическая длина) такое, что для любой строки \(w \in L\) с \(|w| \geq m\) найдётся разбиение \(w = xyz\), для которого:

1. \(|y| \geq 1\) (фрагмент накачки \(y\) непуст)
2. \(|xy| \leq m\) (накачка расположена в начале строки)
3. \(xy^i z \in L\) для всех \(i \geq 0\) (сколько ни повторяй \(y\), строка остаётся в \(L\))

В качестве \(m\) можно взять число состояний FSA, распознающего \(L\).

Набросок доказательства: пусть \(M = (Q, \Sigma, \delta, q_0, F)\) — FSA с \(|Q| = m\), распознающий \(L\). Возьмём \(w \in L\), \(|w| \geq m\). При чтении \(w\) машина проходит не менее \(m+1\) состояния (включая старт). По принципу голубятни какое-то \(q\) повторяется. Пусть путь \[q_0 \xrightarrow{x} q \xrightarrow{y} q \xrightarrow{z} q_f \in F\] Первое повторение происходит не позже чем после прочтения не более \(m\) символов с начала, откуда \(|xy| \leq m\). Так как \(y\) ведёт из \(q\) в \(q\), имеем \(|y| \geq 1\). Из \(\delta^*(q, y) = q\) следует, что накачка \(y\) сколько угодно раз оставляет нас в \(q\), после чего \(z\) ведёт в принимающее. \(\square\)

1.4.2 Необходимое, но не достаточное условие

Лемма о накачке даёт лишь необходимое условие регулярности, не достаточное:

• \(L\) регулярный \(\Rightarrow\) для \(L\) выполняется лемма (гарантированно)
• Лемма выполняется \(\not\Rightarrow\) \(L\) регулярный (у некоторых нерегулярных языков лемма тоже «проходит»!)

Поэтому:

• нельзя по лемме доказать регулярность;
• можно доказать нерегулярность (через контрапозицию).

1.4.3 Контрапозиция: как доказывают нерегулярность

Контрапозиция леммы:

Если для любого \(m \geq 1\) существует \(w \in L\) с \(|w| \geq m\) такая, что при любом разбиении \(w = xyz\) с \(|y| \geq 1\) и \(|xy| \leq m\) найдётся \(i \geq 0\) с \(xy^i z \notin L\), то \(L\) не регулярен.

Это и есть рабочий инструмент. Удобно думать как об игре в двух лиц:

Игрок 1 (противник)	Игрок 2 (вы)
Задаёт любое \(m \geq 1\)	Выбираете \(w \in L\) с \(\|w\| \geq m\)
Задаёт любое разбиение \(w = xyz\) с \(\|y\| \geq 1\) и \(\|xy\| \leq m\)	Находите \(i \geq 0\), что \(xy^iz \notin L\)

Вы выигрываете (язык не регулярен), если всегда можете ответить, как бы ни действовал противник.

1.4.4 Стандартный шаблон доказательства

1. Предположим от противного, что \(L\) регулярен.
2. Пусть \(m \geq 1\) — длина накачки из леммы.
3. Выберите слово \(w \in L\), \(|w| \geq m\) (тактически так, чтобы любое допустимое разбиение «ломало» язык).
4. Рассмотрите произвольное допустимое \(w = xyz\), \(|y| \geq 1\), \(|xy| \leq m\).
5. Используйте \(|xy| \leq m\), чтобы ограничить положение \(y\).
6. Найдите \(i \geq 0\), что \(xy^i z \notin L\).
7. Вывод: лемма нарушена — \(L\) не регулярен.

Самый творческий шаг — выбор \(w\). Удачный выбор заставляет \(y\) состоять из одного типа символов, и накачка легко разрушает структуру языка.

1.4.5 Классический пример: \(L = \{a^n b^n \mid n > 0\}\)

Утверждение: \(L = \{a^n b^n \mid n > 0\}\) не регулярен.

Доказательство:

1. Пусть \(L\) регулярен, \(m\) — длина накачки.
2. Возьмём \(w = a^m b^m \in L\), \(|w| = 2m \geq m\).
3. Любое \(w = xyz\), \(|xy| \leq m\), \(|y| \geq 1\).
4. Первые \(m\) символов \(w\) — все a, значит \(xy\) целиком в блоке a: \(x = a^p\), \(y = a^q\), \(q \geq 1\), \(p + q \leq m\).
5. Тогда \(z = a^{m-p-q} b^m\).
6. При \(i = 2\): \(xy^2 z = a^p \cdot a^{2q} \cdot a^{m-p-q} b^m = a^{m+q} b^m\).
7. Так как \(q \geq 1\), число a больше \(m\), а b ровно \(m\), значит \(xy^2 z \notin L\).

Противоречие с леммой. \(\square\)

Три случая из лекции: можно разобрать все разбиения без опоры только на \(|xy| \leq m\):

• Случай 1: \(y = a^k\) — накачка даёт \(a^{m+k} b^m \notin L\)
• Случай 2: \(y = b^k\) — \(a^m b^{m+k} \notin L\)
• Случай 3: \(y = a^k b^s\) (смешанный) — \(a^{m-k}(a^k b^s)^2 b^{m-s} \notin L\)

1.5 Автоматы с магазином (PDA)

1.5.1 Мотивация: за пределами регулярных языков

Лемма о накачке показывает, что для \(\{a^n b^n\}\) FSA не хватает памяти для «счёта». Нужна модель с большей памятью — естественно добавить стек к FSA, получив автомат с магазином (Pushdown Automaton, PDA).

Иерархия (от слабой к сильной):

• Комбинационная логика (без памяти)
• FSA (конечная память — только состояние)
• PDA (неограниченный стек — контекстно-свободные языки, CFL)
• Машина Тьюринга (лента — всё вычислимое)

PDA ровно на ступень выше FSA; они распознают контекстно-свободные языки, включая вложенные скобки, баланс и т.п.

1.5.2 Что такое стек?

Стек — структура «последним пришёл — первым ушёл» (LIFO), как стопка тарелок: добавлять и снимать можно только сверху.

Стек: push кладёт наверх, pop снимает последний символ

• Push: положить символ наверх.
• Pop: снять верхний (и «прочитать» его).

На дне стека обычно специальный маркер \(Z_0\); по нему проверяют «пустоту» (остался только \(Z_0\)).

Пример — push \(a\), \(b\), \(c\):

Из пустого стека (только \(Z_0\)):

1. После push \(a\): сверху вниз \(a, Z_0\)
2. После push \(b\): \(b, a, Z_0\)
3. После push \(c\): \(c, b, a, Z_0\)
4. После pop: сняли \(c\); осталось \(b, a, Z_0\)

Последний положенный символ снимается первым — свойство LIFO.

Историческая заметка: идею стека ввёл Алан Тьюринг в работе 1946 г. об ACE; операции называл BURY и UNBURY в теории подпрограмм.

1.5.3 Неформальное описание

У FSA есть входная лента и конечное управление (состояние).

PDA то же самое, плюс стек:

• Управление читает следующий символ входа и вершину стека.
• По ним (и по состоянию) переходит в новое состояние и заменяет вершину стека строкой символов.

PDA: конечное управление читает вход и вершину стека, затем обновляет оба

PDA может:

• Пушить (заменить вершину на более длинную строку)
• Попать (заменить вершину на \(\varepsilon\))
• Не менять стек (заменить символ самим собой)
• Делать \(\varepsilon\)-переходы (не двигать головку по входу, только стек)

1.5.4 Формальное определение

PDA — кортеж из 7 компонент:

\[P = (Q,\, \Sigma,\, \Gamma,\, \delta,\, q_0,\, Z_0,\, F)\]

где:

• \(Q\) — конечное множество состояний
• \(\Sigma\) — конечный входной алфавит
• \(\Gamma\) — конечный алфавит магазина
• \(\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \rightarrow \mathcal{P}(Q \times \Gamma^*)\) — функция переходов
• \(q_0 \in Q\) — начальное состояние
• \(Z_0 \in \Gamma\) — начальный символ стека
• \(F \subseteq Q\) — принимающие (финальные) состояния

Чтение перехода: \(\delta(q, a, A) \ni (q', \alpha)\) значит: > В \(q\), прочитав \(a\) из входа (или \(\varepsilon\)), при \(A\) наверху стека: перейти в \(q'\) и заменить \(A\) на строку \(\alpha\).

На стрелках пишут \(a,\, A / \alpha\): «прочитать \(a\), снять \(A\), положить \(\alpha\)».

• Push \(B\) под \(A\): \(A / BA\)
• Pop \(A\): \(A / \varepsilon\)
• Без изменений: \(A / A\)

1.5.5 Шаги PDA

За шаг определяют:

1. Текущее состояние \(q\)
2. Текущий входной символ (или \(\varepsilon\))
3. Вершина стека

За один шаг PDA одновременно:

• меняет состояние на \(q'\)
• двигает головку по входу (или не двигает при \(\varepsilon\))
• заменяет вершину \(A\) на \(\alpha \in \Gamma^*\)

Так как \(\delta\) даёт множество исходов, в общем виде PDA недетерминированы. (PDA детерминирован (DPDA), если \(|\delta(q, a, A)| \leq 1\) и из \(\delta(q, a, A) \neq \emptyset\) следует \(\delta(q, \varepsilon, A) = \emptyset\).)

1.5.6 Условия принятия

• По финальному состоянию: вход исчерпан и PDA в \(q \in F\); содержимое стека не важно.
• По пустому стеку: вход исчерпан и стек «пуст» (только \(Z_0\) или пусто); состояние не важно.

Для недетерминированных PDA оба режима эквивалентны. Для DPDA — не эквивалентны.

Замечание: при приёме по пустому стеку язык должен быть префикс-свободным (ни одна строка языка не является собственным префиксом другой): после опустошения стека продолжить чтение \(wz\) нельзя.

1.5.7 Пошаговый пример: PDA для \(\{a^n b^n \mid n \geq 1\}\)

Идея: по одному a кладём \(A\), по одному b снимаем \(A\). Если после всех b стек ровно «пуст» по смыслу задачи, длины совпали.

Состояния: \(p_0\) (старт), \(p_1\) (читаем a), \(p_2\) (читаем b), \(p_3\) (принятие).

\(\Gamma = \{Z_0, A\}\).

Переходы:

• \(p_0 \to p_1\): \(a,\, Z_0 / AZ_0\)
• \(p_1 \circlearrowleft\): \(a,\, A / AA\)
• \(p_1 \to p_2\): \(b,\, A / \varepsilon\)
• \(p_2 \circlearrowleft\): \(b,\, A / \varepsilon\)
• \(p_2 \to p_3\): \(\varepsilon,\, Z_0 / Z_0\)

Трассировка для aabb:

Шаг	Состояние	Остаток входа	Стек (сверху)	Переход
1	\(p_0\)	\(\mathbf{a}abb\)	\(Z_0\)	\(p_0 \to p_1\): \(a, Z_0/AZ_0\)
2	\(p_1\)	\(\mathbf{a}bb\)	\(A, Z_0\)	\(p_1 \circlearrowleft\): \(a, A/AA\)
3	\(p_1\)	\(\mathbf{b}b\)	\(A, A, Z_0\)	\(p_1 \to p_2\): \(b, A/\varepsilon\)
4	\(p_2\)	\(\mathbf{b}\)	\(A, Z_0\)	\(p_2 \circlearrowleft\): \(b, A/\varepsilon\)
5	\(p_2\)	\(\varepsilon\)	\(Z_0\)	\(p_2 \to p_3\): \(\varepsilon, Z_0/Z_0\)
6	\(p_3\)	\(\varepsilon\)	\(Z_0\)	ПРИНЯТО

---

2. Определения

• Регулярный язык: \(L \subseteq \Sigma^*\), для которого существует FSA \(M\) с \(L = L(M)\).
• Лемма о накачке: для регулярного \(L\) существует \(m \geq 1\): любое \(w \in L\), \(|w| \geq m\), раскладывается \(w = xyz\) с \(|y| \geq 1\), \(|xy| \leq m\) и \(\forall i \geq 0: xy^i z \in L\).
• Длина накачки (\(m\)): можно взять число состояний распознающего FSA.
• Накачка: повторение средней части \(y\) в \(w = xyz\); \(i\) раз даёт \(xy^i z\).
• Контрапозиция леммы: если \(\forall m\) \(\exists w \in L\), \(|w| \geq m\), что для всех допустимых разбиений найдётся \(i\) с \(xy^i z \notin L\), то \(L\) не регулярен.
• Принцип голубятни: \(n\) объектов, \(k < n\) контейнеров — в каком-то контейнере больше одного объекта.
• Цикл в FSA: путь, начинающийся и заканчивающийся в одном состоянии.
• PDA: модель с конечным управлением, входной лентой и стеком; формально 7-кортеж \((Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)\). Распознают ровно CFL.
• Стек: LIFO; операции push и pop.
• Алфавит стека (\(\Gamma\)): конечный; обычно включает \(Z_0\).
• Символ дна стека (\(Z_0\)): маркер дна.
• \(\delta\) PDA: \(\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)\); переход \(\delta(q, a, A) \ni (q', \alpha)\) — прочитать \(a\), заменить \(A\) на \(\alpha\).
• \(\varepsilon\)-переход: без чтения входа.
• Принятие по финальному состоянию: вход исчерпан, состояние \(\in F\).
• Принятие по пустому стеку: вход исчерпан, стек пуст (в смысле определения); для NPDA эквивалентно финальному состоянию.
• Контекстно-свободный язык (CFL): язык, распознаваемый PDA; эквивалентно порождён КС-грамматикой. Всякий регулярный — CFL, обратное неверно.
• NPDA: у \(\delta\) может быть несколько исходов; принятие, если существует успешная ветка.
• DPDA: автомат с магазином, у которого на каждом шаге не более одного возможного перехода: \(|\delta(q, a, A)| \leq 1\) для всех \(q, a, A\); кроме того, если \(\delta(q, a, A) \neq \emptyset\), то \(\delta(q, \varepsilon, A) = \emptyset\) (нельзя одновременно читать символ с входа и делать \(\varepsilon\)-переход с той же вершиной стека).

---

3. Формулы

• Лемма (регулярные): \(\exists m \geq 1\): \(\forall w \in L\), \(|w| \geq m\), \(\exists w = xyz\), \(|y| \geq 1\), \(|xy| \leq m\), \(\forall i \geq 0: xy^iz \in L\)
• Контрапозиция: \(L\) не регулярен, если \(\forall m\) \(\exists w \in L\), \(|w| \geq m\), \(\forall\) допустимых \(w = xyz\) \(\exists i \geq 0: xy^iz \notin L\)
• Длина после накачки: \(|xy^iz| = |w| + (i-1)|y|\)
• Ограничение на \(y\): \(|xy| \leq m\) вынуждает \(y\) лежать в первых \(m\) символах \(w\)
• Нотация переходов PDA: \(a,\, A / \alpha\); для тихого шага: \(\varepsilon, A / \alpha\)
• Формально PDA: \(P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)\), \(\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)\)
• Принятие по финальному состоянию: \(w\) принимается \(\Leftrightarrow\) \(\delta^*(q_0, w, Z_0) \ni (q_f, \gamma)\) для некоторого \(q_f \in F\), \(\gamma \in \Gamma^*\)

---

4. Примеры

4.1. Доказать, что \(L_1 = \{vv^R \mid v \in \{a,b\}^*\}\) не регулярен (Лаба 5, Задание 1)

Докажите леммой о накачке, что \(L_1 = \{vv^R \mid v \in \Sigma_1^*\}\) над \(\Sigma_1 = \{a, b\}\) не регулярен.

(Здесь \(v^R\) — обращение строки \(v\); \(L_1\) — все палиндромы чётной длины над \(\{a,b\}\).)

Показать решение

Идея: \(vv^R\) всегда палиндром. Возьмём \(w = a^m b^{2m} a^m\); накачка в левом блоке a даёт непалиндром.

1. Пусть \(L_1\) регулярен, \(m\) — длина накачки.
2. \(w = a^m b^{2m} a^m \in L_1\) (\(v = a^m b^m\), \(v^R = b^m a^m\)), \(|w| = 4m \geq m\).
3. Произвольное \(w = xyz\), \(|xy| \leq m\), \(|y| \geq 1\).
4. Первые \(m\) символов — a, значит \(y\) из a: \(x = a^p\), \(y = a^k\), \(k \geq 1\), \(z = a^{m-p-k} b^{2m} a^m\).
5. \(i = 0\): \(xy^0 z = a^{m-k} b^{2m} a^m\).
6. Символ на позиции \(m-k+1\) слева — первый b в блоке; справа от конца — всё ещё a при \(k \geq 1\). Не палиндром \(\Rightarrow\) \(\notin L_1\).
7. Вывод: \(L_1\) не регулярен. \(\square\)

Ответ: \(L_1\) не регулярен.

4.2. Доказать, что \(L_2 = \{v \mid \#_a(v) = \#_b(v)\}\) не регулярен (Лаба 5, Задание 2)

Докажите леммой о накачке, что \(L_2 = \{v \in \{a,b\}^* \mid \#_a(v) = \#_b(v)\}\) не регулярен.

Показать решение

Идея: любая строка из \(L_2\) содержит поровну символов a и b. Слово \(a^m b^m\) вынуждает \(y\) лежать в блоке a; накачка вниз убирает часть a, не трогая b, и баланс нарушается.

1. Предположим от противного, что \(L_2\) регулярен. Пусть \(m \geq 1\) — длина накачки.
2. Возьмём \(w = a^m b^m \in L_2\). Тогда \(|w| = 2m \geq m\).
3. Рассмотрим произвольное \(w = xyz\) с \(|xy| \leq m\) и \(|y| \geq 1\).
4. Так как первые \(m\) символов — все a и \(|xy| \leq m\), \(y\) целиком в блоке a: \(y = a^k\), \(k \geq 1\), \(z = a^{m-p-k} b^m\).
5. Возьмём \(i = 0\): \[xy^0 z = xz = a^{m-k} b^m\]
6. Тогда \(\#_a(xy^0 z) = m - k\), \(\#_b(xy^0 z) = m\). При \(k \geq 1\) имеем \(m - k < m\), счётчики не равны, значит \(xy^0 z \notin L_2\).
7. Противоречие с леммой. \(L_2\) не регулярен. \(\square\)

Ответ: \(L_2 = \{v \mid \#_a(v) = \#_b(v)\}\) не регулярен.

4.3. Доказать, что \(L_3 = \{a^{n!} \mid n \geq 0\}\) не регулярен (Лаба 5, Задание 3)

Докажите леммой о накачке, что \(L_3\) над \(\{a\}\) не регулярен.

Показать решение

Идея: факториалы растут быстрее любой линейной прибавки от накачки. Для соседних факториалов \((m+1)! - m! = m \cdot m!\) гораздо больше \(m\) при больших \(m\). Любая накачка с \(|y| \leq m\) не «перепрыгнет» зазор от \(m!\) к \((m+1)!\), и некоторая накачанная строка окажется строго между двумя последовательными факториалами.

1. Пусть \(L_3\) регулярен, \(m \geq 1\) — длина накачки.

2. \(w = a^{m!} \in L_3\), \(|w| = m! \geq m\) при \(m \geq 1\).

3. Произвольное \(w = xyz\), \(|xy| \leq m\), \(|y| \geq 1\).

4. Положим \(|y| = k\), тогда \(1 \leq k \leq m\).

5. Возьмём \(i = m + 1\): \[|xy^{m+1} z| = |w| + m \cdot k = m! + mk\]

6. Нижняя граница: \(m! + mk \geq m! + m > m!\). Верхняя граница: \(m! + mk \leq m! + m^2\). До следующего факториала: \((m+1)! = (m+1)m! = m! + m \cdot m!\). Нужно \(m! + mk < (m+1)!\), т.е. \(k < m!\). При \(m \geq 3\) из \(k \leq m\) следует \(k < m!\). Значит \(m! < m! + mk < (m+1)!\), длина не равна ни одному \(n!\), и \(xy^{m+1} z = a^{m! + mk} \notin L_3\).

   (При \(m = 1\) единственное \(k = 1\); возьмём \(i = 0\): \(|xy^0 z| = 0\), а \(\varepsilon \notin L_3\), так как \(n! \geq 1\) для \(n \geq 0\).)

7. Лемма нарушена, \(L_3\) не регулярен. \(\square\)

Ответ: \(L_3 = \{a^{n!} \mid n \geq 0\}\) не регулярен.

4.4. Доказать, что \(L_4 = \{a^n b^l c^{n+l}\}\) не регулярен (Лаба 5, Задание 4)

Показать решение

Идея: в \(L_4\) число символов c равно сумме чисел a и b. Слово \(a^m b^m c^{2m}\) заставляет \(y\) лежать в блоке a; накачка вниз уменьшает число a, не трогая b и c, и равенство \(n+l\) для c нарушается.

1. Пусть \(L_4\) регулярен, \(m\) — длина накачки.
2. \(w = a^m b^m c^{2m} \in L_4\) (\(n = l = m\), тогда \(n+l = 2m\)), \(|w| = 4m \geq m\).
3. Произвольное \(w = xyz\), \(|xy| \leq m\), \(|y| \geq 1\).
4. Первые \(m\) символов — a, значит \(y = a^k\), \(k \geq 1\), \(z = a^{m-p-k} b^m c^{2m}\).
5. \(i = 0\): \(xy^0 z = a^{m-k} b^m c^{2m}\).
6. Для членства в \(L_4\) нужно \(\#c = (m-k) + m = 2m - k\), но фактически \(\#c = 2m\), при \(k \geq 1\) не совпадает. Значит \(xy^0 z \notin L_4\).
7. \(L_4\) не регулярен. \(\square\)

Ответ: \(L_4 = \{a^n b^l c^{n+l} \mid n, l \geq 0\}\) не регулярен.

4.5. Доказать, что \(L = \{a^n b^n \mid n > 0\}\) не регулярен (Туториал 5, Пример 1)

Показать решение

Идея: \(w = a^m b^m\); ограничение \(|xy| \leq m\) вынуждает \(y\) лежать в блоке a; любая накачка нарушает равенство чисел a и b.

1. Пусть \(L\) регулярен, \(m\) — длина накачки.
2. \(w = a^m b^m \in L\), \(|w| = 2m \geq m\).
3. Произвольное \(w = xyz\), \(|xy| \leq m\), \(|y| \geq 1\).
4. \(xy\) целиком из a: \(x = a^p\), \(y = a^q\), \(q \geq 1\), \(p+q \leq m\), \(z = a^{m-p-q} b^m\).
5. \(i = 2\): \(xy^2 z = a^{m+q} b^m\).
6. При \(q \geq 1\) число a не равно числу b, значит \(xy^2 z \notin L\).
7. \(L\) не регулярен. \(\square\)

Дополнение — три случая без \(|xy| \leq m\): (a) \(y = a^k\) — \(a^{m+k}b^m \notin L\); (b) \(y = b^k\) — \(a^m b^{m+k} \notin L\); (c) \(y = a^k b^s\) — после накачки в середине появляется b перед a, не формат \(a^n b^n\).

Ответ: \(L = \{a^n b^n \mid n > 0\}\) не регулярен.

4.6. Доказать, что \(L_2 = \{a^n b\, a^n\}\) не регулярен (Туториал 5, Пример 2)

Показать решение

Идея: слово \(a^m b\, a^m\); единственный b в центре — «ориентир»: в \(L_2\) ровно один b и поровну a слева и справа. Накачка левого блока a ломает симметрию.

1. Пусть \(L_2\) регулярен, \(m\) — длина накачки.
2. \(w = a^m b\, a^m \in L_2\), \(|w| = 2m + 1 \geq m\).
3. Произвольное \(w = xyz\), \(|xy| \leq m\), \(|y| \geq 1\).
4. Так как \(|xy| \leq m\) и первые \(m\) символов — все a, \(y\) целиком в левом блоке a: \(x = a^p\), \(y = a^q\), \(q \geq 1\), \(z = a^{m-p-q} b\, a^m\), где \(p + q \leq m\).
5. При \(i = 2\): \[xy^2 z = a^p \cdot a^{2q} \cdot a^{m-p-q} b\, a^m = a^{m+q} b\, a^m\]
6. Для членства в \(L_2\) нужно равенство длин левого и правого блоков a, то есть \(m + q = m\), что невозможно при \(q \geq 1\). Значит \(xy^2 z \notin L_2\).
7. Лемма нарушена, \(L_2\) не регулярен. \(\square\)

Ответ: \(L_2 = \{a^n b\, a^n \mid n \in \mathbb{N}\}\) не регулярен.

4.7. PDA для \(L_1 = \{a^n b^n \mid n \geq 1\}\) (Туториал 5, Пример 3)

Показать решение

PDA для aⁿbⁿ

1. PDA: состояния \(p_0, p_1, p_2, p_3\) (принимающее), \(\Gamma = \{Z_0, A\}\).

2. Переходы:

   Переход	Смысл
   \(p_0 \to p_1\): \(a,\, Z_0 / AZ_0\)	Первый a: положить \(A\)
   \(p_1 \circlearrowleft\): \(a,\, A / AA\)	Каждый следующий a: ещё \(A\)
   \(p_1 \to p_2\): \(b,\, A / \varepsilon\)	Первый b: снять \(A\)
   \(p_2 \circlearrowleft\): \(b,\, A / \varepsilon\)	Каждый следующий b: снять \(A\)
   \(p_2 \to p_3\): \(\varepsilon,\, Z_0 / Z_0\)	Конец входа, наверху \(Z_0\) — принять

3. Трассировка \(w =\) aabb: как в табл. разд. 1.5.7 — принято.

4. Корректность: на \(a^n b^n\) кладётся и снимается по \(n\) символов \(A\); при \(k \neq n\) либо остаются \(A\), либо до \(Z_0\) нельзя дойти честно.

Ответ: указанный PDA распознаёт \(L_1 = \{a^n b^n \mid n \geq 1\}\).

4.8. PDA для \(L_2 = \{a^n b\, a^n \mid n \geq 1\}\) (Туториал 5, Пример 4)

Показать решение

PDA для aⁿbaⁿ

1. PDA: \(q_0\) (левые a), \(q_1\) (после единственного b, правые a), \(q_2\) (принимающее); \(\Gamma = \{Z_0, A\}\).

2. Переходы:

   Переход	Смысл
   \(q_0 \circlearrowleft\): \(a,\, Z_0 / AZ_0\)	Первый a слева
   \(q_0 \circlearrowleft\): \(a,\, A / AA\)	Следующие a слева
   \(q_0 \to q_1\): \(b,\, A / A\)	Видим b, не снимая \(A\), переходим к правой части
   \(q_1 \circlearrowleft\): \(a,\, A / \varepsilon\)	Каждый a справа снимает \(A\)
   \(q_1 \to q_2\): \(\varepsilon,\, Z_0 / Z_0\)	Все \(A\) сняты, наверху \(Z_0\) — принять

3. Трассировка aba: \(q_0 \xrightarrow{a,Z_0/AZ_0} q_0\); \(q_0 \xrightarrow{b,A/A} q_1\); \(q_1 \xrightarrow{a,A/\varepsilon} q_1\); \(q_1 \xrightarrow{\varepsilon,Z_0/Z_0} q_2\) — принято.

4. aabaa: аналогично, два push слева, два pop справа — принято.

Ответ: указанный PDA распознаёт \(L_2 = \{a^n b\, a^n \mid n \geq 1\}\).